package com.hyb.algorithm.data.struct.tree;

/**
 *
 * 236. 二叉树的最近公共祖先
 * https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/
 *
 * 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
 *
 * 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，
 * 满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
 * @author: ybhu
 * @create: 2023/12/25 10:39
 */
public class LowestCommonAncestor2 {

    TreeNode res=null;

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        boolean ret=findParent(root,p,q);
        return res;
    }

    public boolean   findParent(TreeNode root, TreeNode p, TreeNode q){

        //递归终止条件
        if(root==null){
            return false;
        }

        //后序遍历
        boolean left=findParent(root.left,p,q);
        boolean right=findParent(root.right,p,q);


        // 在root 左右子树里面 例如：  3->5   3->1    p=5,q=1
        if(left&&right){
            res=root;
        }

        // 在左子树或者右子树里面 并且当前节点node.val== p或者 q  的val  例如：5->2->4   p=5,q=4
        if((left||right)&&(root.val==p.val||root.val==q.val)){
            res=root;
        }

        //如果左边或者右边 包含 则为true   left||right包括 left&&right
        if(left||right){
            return true;
        }

        //如果当前节点包含 也为true
        if(root.val==p.val||root.val==q.val){
            return true;
        }

        return false;
    }
}
